package 剑指offer;

import java.util.Scanner;

/**
 * @description:
 * @author: ywk
 * @date: 2021-03-13
 */
public class 银行家问题 {
    public static int RESOURCE_NUM = 3;
    public static int PROCESS_NUM = 5;
    //系统可用（剩余）资源
    static int[] available = {3, 3, 2};
    //进程最大需求
    static int[][] maxRequest = {{7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 2}, {4, 3, 3}};
    // 进程已占有的资源
    static int[][] allocation = {{0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}};
    // 进程还需要的资源
    static int[][] need = {{7, 4, 3}, {1, 2, 2}, {6, 0, 0}, {0, 1, 1}, {4, 3, 1}};
    // 是否安全
    static boolean[] Finish = new boolean[PROCESS_NUM];
    // 安全序列号
    static int[] safeSeries = {0, 0, 0, 0, 0};
    // 进程请求资源量
    static int[] request = new int[RESOURCE_NUM];
    // 进程数量计数
    static int num;

    static void showInfo() {
        System.out.println("-----------------");
        System.out.println("当前系统各类资源剩余：");
        for (int j = 0; j < RESOURCE_NUM; j++) {
            System.out.print(available[j] + "\t");
        }
        System.out.println("\n\n当前系统资源情况：\n");
        System.out.println("PID\tMax\t\tAllocation\tNeed\n");
        for (int i = 0; i < PROCESS_NUM; i++) {
            System.out.print(i + "\t");
            for (int j = 0; j < RESOURCE_NUM; j++) {
                System.out.print(maxRequest[i][j]);
            }
            System.out.print("\t\t");
            for (int j = 0; j < RESOURCE_NUM; j++) {
                System.out.print(allocation[i][j]);
            }
            System.out.print("\t\t");
            for (int j = 0; j < RESOURCE_NUM; j++) {
                System.out.print(need[i][j]);
            }
            System.out.println();
        }
    }

    //打印安全检查信息
    static void safeInfo(int[] work, int i) {
        int j;
        System.out.print(i);
        System.out.print("\t\t");
        for (j = 0; j < RESOURCE_NUM; j++) {
            System.out.print(work[j]);
        }
        System.out.print("\t\t");
        for (j = 0; j < RESOURCE_NUM; j++) {
            System.out.print(allocation[i][j]);
        }
        System.out.print("\t\t");
        for (j = 0; j < RESOURCE_NUM; j++) {
            System.out.print(need[i][j]);
        }
        System.out.print("\t\t");
        for (j = 0; j < RESOURCE_NUM; j++) {
            System.out.print(allocation[i][j] + work[j]);
        }
        System.out.println();
    }    //判断一个进程的资源是否全为零

    static boolean isAllZero(int kang) {
        num = 0;
        for (int i = 0; i < RESOURCE_NUM; i++) {
            if (need[kang][i] == 0) {
                num++;
            }
        }
        return num == RESOURCE_NUM;
    }

    //安全检查
    static boolean isSafe() {
        //int RESOURCE_NUMFinish = 0;
        int safeIndex = 0;
        int allFinish = 0;
        int[] work = new int[RESOURCE_NUM];
        int r = 0;
        int temp = 0;
        int pNum = 0;
        //预分配为了保护available[]
        for (int i = 0; i < RESOURCE_NUM; i++) {
            work[i] = available[i];
        }        //把未完成进程置为false
        for (int i = 0; i < PROCESS_NUM; i++) {
            boolean result = isAllZero(i);
            if (result == true) {
                Finish[i] = true;
                allFinish++;
            } else {
                Finish[i] = false;
            }
        }
        //预分配开始
        while (allFinish != PROCESS_NUM) {
            num = 0;
            for (int i = 0; i < RESOURCE_NUM; i++) {
                if (need[r][i] <= work[i] && Finish[r] == false) {
                    num++;
                }
            }
            if (num == RESOURCE_NUM) {
                for (int i = 0; i < RESOURCE_NUM; i++) {
                    work[i] = work[i] + allocation[r][i];
                }
                allFinish++;
                safeInfo(work, r);
                safeSeries[safeIndex] = r;
                safeIndex++;
                Finish[r] = true;
            }
            r++;
            //该式必须在此处
            // 做一个循环
            if (r >= PROCESS_NUM) {
                r = r % PROCESS_NUM;
                //循环一次后，数量还是没有变化，则退出,说明分配失败
                if (temp == allFinish) {
                    break;
                }
                temp = allFinish;
            }
            pNum = allFinish;
        }        //判断系统是否安全
        for (int i = 0; i < PROCESS_NUM; i++) {
            if (Finish[i] == false) {
                System.out.print("\n当前系统不安全！\n\n");
                return false;
            }
        }        //打印安全序列
        System.out.print("\n当前系统安全！\n\n安全序列为：");
        for (int i = 0; i < PROCESS_NUM; i++) {
            boolean result = isAllZero(i);
            if (result == true) {
                pNum--;
            }
        }
        for (int i = 0; i < pNum; i++) {
            System.out.print(safeSeries[i]);
        }
        return true;
    }

    //主函数
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int curProcess = 0;
        int a = 0;
        showInfo();
        System.out.print("\n系统安全情况分析\n");
        System.out.print(" PID\t Work\t\tAllocation\t Need\t\tWork+Allocation\n");
        boolean isStart = isSafe();
        //用户输入或者预设系统资源分配合理才能继续进行进程分配工作
        while (isStart) {
            //限制用户输入，以防用户输入大于进程数量的数字，以及输入其他字符（乱输是不允许的）
            do {
                if (curProcess >= PROCESS_NUM || a < 0) {
                    System.out.print("\n请不要输入超出进程数量的值或者其他字符：\n");
                    while (!scanner.next().equals('\n')) {
                    }
                    //清空缓冲区
                }
                System.out.print("\n------------------------------------------------------------------------------------\n");
                System.out.print("\n输入要分配的进程：");
                a = curProcess = scanner.nextInt();
                System.out.print("\n");
            }
            while (curProcess >= PROCESS_NUM || a < 0);
            //限制用户输入，此处只接受数字，以防用户输入其他字符（乱输是不允许的）
            a = 1;
            for (int i = 0; i < RESOURCE_NUM; i++) {
                do {
                    if (a == 0) {
                        System.out.print("\n请不要输入除数字以外的其他字符，请重新输入：\n");
                        while (!scanner.next().equals('\n')) {
                        }
                        //清空缓冲区
                    }
                    System.out.print("请输入要分配给进程 " + curProcess + "的第" + (i + 1) + " 类资源：");
                    a = scanner.nextInt();
                    request[i] = a;
                } while (a == 0);
            }
            //判断用户输入的分配是否合理，如果合理，开始进行预分配
            num = 0;
            for (int i = 0; i < RESOURCE_NUM; i++) {
                if (request[i] <= need[curProcess][i] && request[i] <= available[i]) {
                    num++;
                } else {
                    System.out.print("\n发生错误！可能原因如下：\n(1)您请求分配的资源可能大于该进程的某些资源的最大需要！\n(2)系统所剩的资源已经不足了！\n");
                    break;
                }
            }
            if (num == RESOURCE_NUM) {
                num = 0;
                for (int j = 0; j < RESOURCE_NUM; j++) {
                    //分配资源
                    available[j] = available[j] - request[j];
                    allocation[curProcess][j] = allocation[curProcess][j] + request[j];
                    need[curProcess][j] = need[curProcess][j] - request[j];
                    //记录分配以后，是否该进程需要值为0了
                    if (need[curProcess][j] == 0) {
                        num++;
                    }
                }
                //如果分配以后出现该进程对所有资源的需求为0了，即刻释放该进程占用资源（视为完成）
                if (num == RESOURCE_NUM) {
                    //释放已完成资源
                    for (int i = 0; i < RESOURCE_NUM; i++) {
                        available[i] = available[i] + allocation[curProcess][i];
                    }
                    System.out.print("\n\n本次分配进程 P%d 完成,该进程占用资源全部释放完毕！\n" + curProcess);
                } else {
                    //资源分配可以不用一次性满足进程需求
                    System.out.print("本次分配进程" + curProcess + "未完成！\n");
                }
                showInfo();
                System.out.print("\n系统安全情况分析\n");
                System.out.print(" PID\t Work\t\tAllocation\t Need\t\tWork+Allocation\n");

                //预分配完成以后，判断该系统是否安全，若安全，则可继续进行分配，若不安全，将已经分配的资源换回来
                if (!isSafe()) {
                    for (int j = 0; j < RESOURCE_NUM; j++) {
                        available[j] = available[j] + request[j];
                        allocation[curProcess][j] = allocation[curProcess][j] - request[j];
                        need[curProcess][j] = need[curProcess][j] + request[j];
                    }
                    System.out.print("资源不足，等待中...\n\n分配失败！\n");
                }
            }
        }
    }
}

